package demo2;

/**
 * 最长回文子串
 * 给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。
 *
 * 输入: "babad"
 * 输出: "bab"
 * 注意: "aba" 也是一个有效答案。
 *
 * 输入: "cbbd"
 * 输出: "bb"
 */
public class LongestPlainString {
    public static void main(String[] args) {
        String s1 = "babad";
        System.out.println(theLongestPlainString(s1));
        String s2 = "cbbd";
        System.out.println(theLongestPlainString(s2));
    }

    public static String theLongestPlainString(String s){
        if(s.length()==0) return s;

        int res = 1; // 记录最长回文串的长度
        int ll = 0; // 记录最长回文串的起始位置
        int rr = 0; // 记录最长回文串的终止位置

        for (int i = 0; i < s.length()-1; i++) {

            // 情况1：首先以i为中心
            int l = i-1;
            int r = i+1;
            while(l >= 0 && r < s.length() && s.charAt(l) == s.charAt(r)){
                int len = r - l + 1;
                if(len > res){
                    res = len;
                    ll = l;
                    rr = r;
                }
                l--;
                r++;
            }

            // 情况2：以i和i+1为中心 "cbbd"这种
            l = i;
            r = i+1;
            while(l >= 0 && r < s.length() && s.charAt(l) == s.charAt(r)){
                int len = r - l + 1;
                if(len > res){
                    res = len;
                    ll = l;
                    rr = r;
                }
                l--;
                r++;
            }
        }

        return s.substring(ll,rr+1);
    }
}
